package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         740,
		Discription: "每次选一个nums[i]并获得对应的值，但要删除值为nums[i]-1和nums[i]+1的所有元素，这样操作最终获得的最大值",
		Level:       2,
		Labels: map[string]int{
			"哈希表":   1,
			"多元排序":  1,
			"动态规划":  1,
			"有限状态机": 1,
		},
	})
}

//统计每个值的出现次数
//按值大小给[值，出现次数]排序
//转化成打家劫舍
func DeleteAndEarn(nums []int) int {
	valMap := make(map[int]int, 0)
	for _, val := range nums {
		valMap[val]++
	}

	vals := make([][2]int, len(valMap))
	i := 0
	for val, count := range valMap {
		vals[i] = [2]int{val, count}
		i++
	}

	sort.Slice(vals, func(i, j int) bool {
		return vals[i][0] < vals[j][0]
	})

	dp := make([][2]int, len(vals))
	dp[0] = [2]int{0, vals[0][0] * vals[0][1]}
	for i := 1; i < len(vals); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1])
		if vals[i-1][0]+1 == vals[i][0] {
			dp[i][1] = dp[i-1][0] + vals[i][0]*vals[i][1]
		} else {
			dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + vals[i][0]*vals[i][1]
		}
	}

	return max(dp[len(vals)-1][0], dp[len(vals)-1][1])
}
